/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package phd.dupenois.datatrees.tree2d;

import uk.co.dupenois.geometry.CoordinateList;
import java.util.Vector;
import phd.dupenois.changeidentifiers.dotpatterns.Range;

/**
 *
 * @author mpd209
 */
public class Tree2D {
    private int height;
    private int width;
    private Node2D rootNode;
    public Tree2D(Node2D rootNode, int width, int height){
        this.rootNode = rootNode;
        this.height = height;
        this.width = width;
    }

 
    public Vector<Node2D> search(Range range){
        return this.rootNode.search(range);
    }

    public static Tree2D buildTree(CoordinateList points){
        HEIGHT_COUNT = -1;
        Object[] result = buildTree(points, 0, 0, null);
        return new Tree2D((Node2D)result[0], (Integer)result[1], (Integer)result[2]);
    }
    private static int HEIGHT_COUNT;
    private static Object[] buildTree(CoordinateList points, int depth, int width, Node2D parent){
        if(points.size()<1)return null;
        HEIGHT_COUNT = (HEIGHT_COUNT < depth ? depth : HEIGHT_COUNT);
        CoordinateList p1;
        CoordinateList p2;
        Node2D node = new Node2D();
        node.setParent(parent);
        node.setDistanceFromTop(HEIGHT_COUNT);
        Range range;
        if(points.size() == 1){
            node.setValue(points.getFirstFromX());
            return new Object[]{node, width, HEIGHT_COUNT+1};
        }else if(depth%2==0){
            node.setHorizontal(true);
            CoordinateList[] subLists = points.splitByX();
            p1 = subLists[0];
            p2 = subLists[1];
            range = new Range(points.getFirstFromX(), points.getLastFromX());
        }else{
            node.setHorizontal(false);
            CoordinateList[] subLists = points.splitByY();
            p1 = subLists[0];
            p2 = subLists[1];
            range = new Range(points.getFirstFromY(), points.getLastFromY());
        }
        node.setRange(range);
        Object[] left = buildTree(p1, depth+1, width, node);
        node.setLeft((Node2D)left[0]);

        Object[] right = buildTree(p2, depth+1, width, node);
        node.setRight((Node2D)right[0]);
        return new Object[]{node, width, HEIGHT_COUNT+1};
    }

    /**
     * @return the height
     */
    public int getHeight() {
        return height;
    }

    /**
     * @return the width
     */
    public int getWidth() {
        return width;
    }

    /**
     * @return the rootNode
     */
    public Node2D getRootNode() {
        return rootNode;
    }
    


    

}
